#include <stdlib.h>
#include <stdio.h>
#define MAX_NUM 4   //(2,4) B 树
#define NULL 0
#define Nonesense -1000   //初始值为-1000，，无意义
typedef struct  BTNode
{

    struct BTNode * parent;
    int key[MAX_NUM] ;  //关键码向量,最大值应为MAX_NUM-1 ,多出一个是为了插入时临时存储
    struct BTNode * child[MAX_NUM+1]; // 孩子向量最大值应为MAX_NUM ,多出一个是为了插入时临时存储
    int key_num;//关键码实际数量
    int child_num; // 孩子向量实际数量
    /* data */
} BTNode;


typedef struct BTree
{
    int _size ; //存放的关键码总数
    int _order ; //B树的阶次
    BTNode * _root ;//根节点
    BTNode * _hot ;// BTree:: search() 最后访问的非空 的节点位置
}BTree;

/*
参数: array数组  array_num 数组元素长度   e 需要寻找的元素
      array 递增排列
返回：若找到 则返回秩；若未找到，则返回第一个大于e的元素的秩(该秩可以作为 需要寻找的 child 的秩)
      至于有没有找到，可由调用者判断
*/
int array_find(int array[],int array_num,int e)
{
    int i;
    for( i =0;i<array_num ;i++)
    {
        if(e==array[i] || e<array[i])
            return i;
    }
    return i;
}

/* BTree_search 搜索BTree
    若成功 ，则返回 BTNode
    若失败，则返回NULL ，_hot 记录最后查找失败节点
*/
BTNode * BTree_search(BTree * tree , int e)
{
    printf("BTree_search start \n");
    BTNode * v = tree->_root;
    tree->_hot = NULL;
    while (v!= NULL)
    {
        int rank = array_find(v->key, v->key_num,e);

        printf("rank %d  \n",rank);
        for(int i=0;i<v->key_num;i++)
        {
            printf ("%d  ",v->key[i]);
        }
        if( rank<v->key_num  )
        {
            if (v->key[rank] ==e ) //找到
                return v;
            else
            {
                tree->_hot = v;
                v =  v->child[rank];
                //printf("BTree_search %d  %d\n",v,v->child[rank]);
            }
        }
        else
        {
            tree->_hot = v;
            v =  v->child[rank];
        }
    }

    printf("BTree_search 未找到\n");
    return NULL ;
}

BTree* BTree_Create()
{
    BTree * temp = (BTree*) malloc(sizeof(BTree));
    temp->_size =0;
    temp->_order = MAX_NUM;
    temp->_root = NULL;
    temp->_hot = NULL;

    return temp;
}
BTNode * BTNode_Create()
{
    BTNode * temp = (BTNode *) malloc(sizeof(BTNode));
    temp->child_num =0;
    temp->key_num = 0;
    temp->parent = 0;
    int i=0;
    for(i=0;i<MAX_NUM;i++)
    {
        temp->child[i] ==(BTNode *)0;
    }
    return temp;
}


/*
    index 需要插入的位置 秩
*/
array_Int_Insert(int * arr,int num,int index,int e)
{
    int i ;
    for(i=num;i>=index;i--)
    {
        arr[i+1] = arr[i];
    }
    arr[index] = e;
}

array_point_Insert(BTNode *arr [],int num,int index,BTNode *  e)
{
    int i ;
    for(i=num;i>=index;i--)
    {
        arr[i+1] = arr[i];
    }
    arr[index] = e;
}


void BTNode_Insert_END( BTNode * node,int e)
{
    if(!node)
        return;
    printf("此时BTNode_key :");
    for(int i=0;i<node->key_num;i++)
    {
        printf("%d ",node->key[i]);
    }
    printf("\n");

    int rank = array_find(node->key,node->key_num, e);
    printf("BTNode_Insert_END  %d,插入数值 %d\n",rank,e);
    array_Int_Insert(node->key,node->key_num,rank,e);
    array_point_Insert(node->child,node->child_num,rank+1,(BTNode*) 0);

    node->child_num ++;
    node->key_num ++;

    printf("此时BTNode_key :");
    for(int i=0;i<node->key_num;i++)
    {
        printf("%d ",node->key[i]);
    }
    printf("\n");

}

void solveOverFlow(BTree* tree, BTNode *node)
{
    if (node->key_num > tree->_order -1)  //key的数量达到 MAX_NUM -1 上限，发生上溢
    {
        printf("上溢处理开始\n");
        printf("上溢 结点数量 %d\n",node->key_num);

        int rank_keyOverFlow = ceil((node->key_num-1)/2)+1;
        printf("上溢结点 rank %d, 值 %d\n",rank_keyOverFlow,node->key[rank_keyOverFlow]);

        BTNode * newNode = BTNode_Create();
        tree->_size ++;
        //分类结点
        int k=0;
        for (int j= rank_keyOverFlow +1;j<node->key_num;j++)
        {
            printf("结点 值 %d进行分裂\n",node->key[j]);
            newNode->key[k] = node->key[j];
            newNode->key_num ++;
            k++;

        }
        //child结点
        k=0;
        for (int j= rank_keyOverFlow +1;j<node->child_num;j++)
        {
            newNode->child[k] = node->child[j];
            newNode->child_num ++;
            k++;
        }

        node->key_num = rank_keyOverFlow;
        node->child_num = rank_keyOverFlow+1;
        //若没有父节点
        if( node->parent == NULL)
        {
            printf("没有父节点\n");
            BTNode * parent = BTNode_Create();
            parent->key[0] = node->key[rank_keyOverFlow];
            parent->child[0] = node;
            parent->child[1] = newNode;

            parent->key_num = 1;
            parent->child_num = 2;

            newNode->parent = parent;
            node->parent = parent;

            tree->_size ++;
            tree->_root = parent;
            solveOverFlow(tree,parent);
        }
        //若有父节点,则插入父结点中
        else
        {
            printf("有父节点,则插入父结点中\n");
            BTNode * parent = node->parent;
            int rank=  array_find(parent->key,parent->key_num, node->key[rank_keyOverFlow]);
            array_Int_Insert(parent->key,parent->key_num,rank ,node->key[rank_keyOverFlow]);
            parent->key_num ++;
            parent->child[rank] = node;
            array_point_Insert(parent->child,parent->child_num,rank+1,newNode);
            parent->child_num ++ ;
            solveOverFlow(tree,parent);
        }
    }
};

//
void BTree_Insert(BTree * tree,int e)
{
    if(tree->_root == NULL)
    {
        printf(" Create root\n");
        tree->_root =BTNode_Create();
    }
    printf("BTree_Insert start \n");


    BTNode * temp_node =  BTree_search(tree, e);
    printf("BTree_Insert start2 \n");
    if(!temp_node) //若未找到 BTree 中的e，，则tree->_hot 则是应该插入的节点
    {
        printf("未找到e\n");
        temp_node = tree->_hot;
    }
    else
        return;

    BTNode_Insert_END(temp_node,e);
    solveOverFlow(tree , temp_node);
}


int main()
{
    BTree * tree = BTree_Create();
    BTree_Insert(tree,10);

   // BTree_Insert(tree,20);
   // BTree_Insert(tree,30);
  //  BTree_Insert(tree,40);
  //  BTree_Insert(tree,50);
 //  BTree_Insert(tree,60);
 //   BTree_Insert(tree,70);
 //   BTree_Insert(tree,80);
    BTree_Insert(tree,5);
    //BTree_Insert(tree,15);
   // BTree_Insert(tree,25);

    for( int i =0;i<tree->_root->key_num;i++)
    {
        printf("%d ",tree->_root->key[i]);
    }
    printf("\n");
    if(tree->_root ->child[0])
    {
        BTNode *v = tree->_root->child[0];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");

    if(tree->_root ->child[1])
    {
        BTNode *v = tree->_root->child[1];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");
if(tree->_root ->child[2])
    {
        BTNode *v = tree->_root->child[2];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");

    if(tree->_root ->child[3])
    {
        BTNode *v = tree->_root->child[3];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }

    BTree_Insert(tree,29);
BTree_Insert(tree,2);

     for( int i =0;i<tree->_root->key_num;i++)
    {
        printf("%d ",tree->_root->key[i]);
    }
    printf("\n");
    if(tree->_root ->child[0])
    {
        BTNode *v = tree->_root->child[0];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");

    if(tree->_root ->child[1])
    {
        BTNode *v = tree->_root->child[1];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");
if(tree->_root ->child[2])
    {
        BTNode *v = tree->_root->child[2];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }
    printf("         ");

    if(tree->_root ->child[3])
    {
        BTNode *v = tree->_root->child[3];
        for( int i =0;i<v->key_num;i++)
        {
            printf("%d ",v->key[i]);
        }
    }

    return 0;
}
